/*     nloc2.c  
       (c) Copyright 1996.  James Archibald.
       Brigham Young University.


   This code computes the locality of an input trace in byutr format.
   The formulation of locality used is as follows.  The algorithm
   counts locality events, which can be thought of as directed arcs
   from one reference to another (from "base" address to "sink"
   address), always in the forward trace direction.  Locality events
   computed here do not include any additional occurrences of either
   the base or the sink address.  Therefore, from the point of view of
   the sink reference, the base is always the last occurrence of a
   reference to that particular address.  Similarly, from the point of
   view of the base reference, the sink is the next occurrence of a
   reference to the sink address. This simplification allows locality
   to be computed in the forward direction, so nasty issues of trace
   flipping can be avoided.  Locality can now be computed on the fly
   as a trace is collected.  

   This version computes locality entirely from a reference stack (MRU
   on top) and automatically gives you the entire locality surface
   (not limited to -256 to +256 strides).  As a first pass, I'll keep
   the same number of bins but add an overflow bin on the side to
   handle all outliers.

   nloc2.c differs from nloc1.c in that the code is simplified (the
   list is singly-linked) and that we are not simultaneously computing
   delay.  I'm trying to get it as fast as possible in this version.
   (Stats are minimized, for instance.)

   Addresses are assumed to be byte addresses and shifted to make word
   addresses, and locality is computed at the word level.  Modify by
   changing ADDRSHIFT at top of file.  

   This benchmark was changed slightly for compilation by lcc which
   doesn't get bit unions correct (at least version 3.5 doesn't).
   Eight separate bit fields were replaced by a single unsigned char
   so that the size of the byutr structure read is correct (12 bytes).
   The only part of the structure used to compute locality is addr, so
   it has no other impact.                            */


#include <stdio.h>

typedef	struct t_byutr
{
	unsigned long	addr;	/* Address, except when special bit is set */
	unsigned long	data;	/* Data field, except when special bit is set */
	unsigned short	dt;	/* 1 less than # of cycles since last ref */
	unsigned char junk;	/* lumps together multiple bit fields  */
} 	byutr;

#define REV_NUM 2.0		/* singly-linked list, only ws kept */

#define STRIDE_VALS 19		/* number of unique bins for */
#define DELAY_VALS  26		/* quantization */
#define STRIDE_RANGE 513	/* count of unique strides to track */

#define ADDRSHIFT 2		/* currently going from byte to word
				   address */

struct st_node2
{
    unsigned long ref_addr;	/* tag for this entry */
    struct st_node2 *stfoll;	/* ptr to next node in stack list */
};

struct st_node2 *stacktop;	/* head ptr of list */
unsigned long unique_cnt;	/* total number of unique refs seen */
unsigned long curr_index;	/* global reference count */

long wstally[STRIDE_VALS][DELAY_VALS]; /* tallies by working set size,
					  or unique references */

int stride_map[STRIDE_RANGE];	/* maps stride to index in tally */
                                /* stride+256 gets entry for stride */
				/* handy way to map with different ranges */

/* the number of elements in stride dimension in each bin */
int bin_size[STRIDE_VALS] = { 128, 64, 32, 16, 8, 4, 2, 1, 1, 1, 1, 1,
				  2, 4, 8, 16, 32, 64, 128 };

/* the number of elements in delay dimension in each bin */
int d_bin_size[DELAY_VALS] = { 1, 1, 2, 4, 8, 16, 32, 64, 128, 256,
				   512, 1024, 2048, 4096, 8192, 16384,
				   32768, 65536, 131072, 262144,
				   524288, 1048576, 2097152, 4194304,
				   8388608, 16777216 };

init_s_map()			/* initializes stride_map */
{
    int i,j,k;
    /* do stride of zero */
    stride_map[256] = 9;
    /* do positive and negative strides together */
    for (i=1; i<=256; i++)
    {
	for (j=1,k=0x01; i>k ; j++,k=(k<<1));
	stride_map[i+256] = 9+j;
	stride_map[256-i] = 9-j;
    }
}

/* init_s_map() initializes to these values: -256 to -129: 0; -128 to */
/* -65: 1; -64 to -33: 2; -32 to -17: 3; -16 to -9: 4; -8 to -5: 5; -4 */
/* to -3: 6; -2: 7; -1: 8; 0: 9; 1: 10; 2: 11; 3 to 4: 12; 5 to 8: 13; */
/* 9 to 16: 14; 17 to 32: 15; 33 to 64: 16; 65 to 128: 17; 129 to 256: */
/* 18 */

init_tally()
{
    int i,j;
    for (i = 0; i < STRIDE_VALS; i++)
    {
	for (j = 0; j < DELAY_VALS; j++)
	{
	    wstally[i][j] = 0;
	}
    }
}

print_res()
{
    char buf[20];
    int i, j, res;
    if (curr_index == 1) 
	printf("No input values\n");
    else
    {
	printf("\t\tNew Locality (ws), revision number: %.1f\n\n", REV_NUM);

	/* do header for strides */
	printf("   -256-128");
	for (j = -64; j < -1; j = j / 2)
	    printf(" %3i", j);
	printf("  -1   0");
	for (j = 1; j <= 256; j = j * 2)
	    printf(" %3i", j);
	printf("\n");

	/* now do row by row */
	for (i = 0; i < DELAY_VALS; i++)
	{
	    printf("%2i ", i);
	    for (j = 0; j < STRIDE_VALS; j++) /* DON'T flip around s=0 */
	    {
		if (wstally[j][i] > 0)
		{
		    res = 100.0 * 
			((double) wstally[j][i] / (double) bin_size[j]) 
			    / (double) (curr_index-1);
		    sprintf(buf,"  %02i", (int) res);
		    if (buf[2] == '0' && buf[3] == '0')
			printf("   -");
		    else
			printf(buf);
		}
		else
		    printf("    ");
	    }
	    printf("\n");
	}

	printf("\nNumber of references seen: %lu\n", curr_index-1);
	printf("Number of unique references: %lu\n", unique_cnt);
    }
}

main()
{
    int counter, i, j, stride, found;
    unsigned long depth, k;

    struct st_node2 *xxx;	/* tmps for walking stack entries */
    struct st_node2 *prev;

    byutr rec;
    FILE *fp;

    init_s_map();
    init_tally();

    counter = 0;		/* used only to output progress info */
    curr_index = 1;
    stacktop = NULL;
    unique_cnt = 0;

    fp = fopen("sample.tr", "r");
    if (fp == NULL)
    {
	fprintf(stderr, "couldn't open sample.tr trace file \n");
	exit(-1);
    }
    while (fread(&rec,sizeof(byutr),1,fp) == 1)
    {
	/* first, shift byte address to make word address */
	/* this may need to be modified for each trace format */

	rec.addr = rec.addr>>ADDRSHIFT;


	/* now, traverse stack list, tallying locality events for
	   every reference until the last occurrence of this address,
	   or until the end of the list.  */

	xxx = stacktop;
	prev = NULL;
	depth = 1;
	found = 0;

	while (xxx != NULL)
	{
	    if (xxx->ref_addr == rec.addr)
	    {
		found = 1;
		/* completes locality event to itself, update both
		   dtally and wstally */
		i = stride_map[256];
		for (j = 0, k = 0x01; depth > k; j++, k = (k<<1));
		wstally[i][j]++;

		/* now move entry to top of stack and update fields */
		if (prev != NULL)
		{
		    prev->stfoll = xxx->stfoll;
		    xxx->stfoll = stacktop;
		    stacktop = xxx;
		}
		/* else already at stack top so do nothing */
		break;		/* traverse is complete: exit */
	    }
	    else 
	    {
		/* update both tallys.  first determine difference in
		   stride since it is used for both */
		stride = rec.addr - xxx->ref_addr;
		if (stride <= 256 && stride >= -256)
		{		/* in range -- update tallys */
		    i = stride_map[stride+256];
		    for (j = 0, k = 0x01; depth > k; j++, k = (k<<1));
		    wstally[i][j]++;
		}
		/* else do nothing at this point -- later will add
		   code here to trace things outside of current stride
		   range */ 
	    }
	    prev = xxx;
	    xxx = xxx->stfoll;
	    depth++;
	}

	if (!found)
	{			/* make a new entry at stacktop */
	    xxx = (struct st_node2 *) malloc(sizeof(struct st_node2));
	    xxx->ref_addr = rec.addr;
	    xxx->stfoll = stacktop;
	    stacktop = xxx;
	    unique_cnt++;
	}

	/* update counters */
	curr_index++;

	/* output indication of progress every 10K refs */
	if (++counter > 20000)
	    break;
    }
    fclose(fp);
    /* now print to stdout in a decent format, dividing by */
    /* the size of each bin (number of distinct strides contained) */
    /* and all bins by the length of the trace (curr_index) */

    print_res();
}

